package hot

/*
*
300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

思路:
由于子序列本质上是数组的一个子集, 那么使用子集型回溯来思考
对于子集型回溯, 有[选或不选]以及[枚举选哪个]这两种思路

例如[1,6,7,2,4,5,3]这个序列
如果倒着思考, 假设3是子序列的最后一个数,
考虑选或不选的话, 前面的数字就需要和3比较大小
所以需要直到当前下标以外, 还需要知道序列上一个数字的下标

而如果考虑枚举选哪个, 可以直接枚举前面的比3小的数字, 当作子序列的倒数第二个数,
那么只需要知道当前所选的数字的下标即可

这样对比, [枚举选哪个]这种思路, 只需要一个参数, 更加好写

具体实现步骤:
1.从刚才的思考过程, 可以总结出这样的子问题
定义 dfs(i), 表示以 nums[i]结尾的 LIS长度,

	那么枚举满足要求的 nums[j],
	问题就变成了以 nums[j]结尾的 LIS长度
	那么把这些子问题求一个最大值, 然后再加上 nums[i]这1个数字,
	就得到了以 nums[i]结尾的 LIS长度

思路:
1.状态定义: dp[i] 的值代表 nums前i个数字的最长子序列长度
2.转移方程, 将j从0到i遍历, 计算新的dp[i], 遍历列表区间做以下判断,

	当 nums[i] > nums[j]时, nums[i]可以接在nums[j]之后(此题要求严格递增), 此情况下最长上升子序列长度为dp[j] + 1
	当 nums[i] <= nums[j]时, nums[i]无法接在 nums[j]之后, 此情况上升子序列不成立, 跳过

3.然后比较dp[j] + 1 与 dp[j]比较, 用较大值重新赋值
*/
func lengthOfLIS(nums []int) int {
	var dp = make([]int, len(nums)) //1.声明dp数组

	dp[0] = 1 //2.dp[0]赋值, 声明返回结果max
	res := 1

	for i := 1; i < len(nums); i++ { //3.从下标1开始, 遍历nums依次取值
		dp[i] = 1 //先将dp[i]赋值为1

		//从0位置一直找到i位置
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] { //如果当前i位置 > 前面的j位置数
				if dp[j]+1 > dp[i] { //如果前面dp[j]的数量 + 1 > 当前dp[i],那么将当前位置重新赋值为dp[j]+1
					dp[i] = dp[j] + 1
				}
			}
		}

		if dp[i] > res { //更新最大结果值
			res = dp[i]
		}
	}
	return res
}
